package leetcode;

import java.util.*;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2022-01-24 19:16
 **/
public class LeetCode2045 {

    public static void main(String[] args) {
        LeetCode2045 code = new LeetCode2045();
        System.out.println(code.secondMinimum(5, new int[][]{{1,2},{1,3},{1,4},{3,4},{4,5}}, 3, 5));
    }

    public int secondMinimum(int n, int[][] edges, int time, int change) {
        List<Integer>[] lists = new List[n + 1];
        for (int i = 1; i <= n; i++) {
            lists[i] = new ArrayList<>();
        }

        for (int[] edge : edges) {
            lists[edge[0]].add(edge[1]);
            lists[edge[1]].add(edge[0]);
        }

        // path[i][0] 表示从 1 到 i 的最短路长度，path[i][1] 表示从 1 到 i 的严格次短路长度
        int[][] path = new int[n + 1][2];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(path[i], Integer.MAX_VALUE);
        }

        Queue<int[]> q = new ArrayDeque<>();
        //将起点添加到队列中
        q.offer(new int[]{1, 0});

        //当path[n][1]不为Integer.MAX_VALUE时,说明出现了严格次短路径,
        while (path[n][1] == Integer.MAX_VALUE) {
            int[] poll = q.poll();
            //当前节点
            int cur = poll[0];
            //从点1到当前点的距离
            int len = poll[1];

            //遍历当前节点可到达的下一个节点
            for (int next : lists[cur]) {
                if (len + 1 < path[next][0]) {
                    path[next][0] = len + 1;
                    //如果是点1到达next点的最短路径,将其添加到队列中
                    q.offer(new int[]{next, len + 1});
                } else if (len + 1 < path[next][1] && len + 1 > path[next][0]) {
                    path[next][1] = len + 1;
                    //如果是点1到达next点的严格次短路径,将其添加到队列中
                    q.offer(new int[]{next, len + 1});
                }
            }
        }

        int res = 0;
        //path[n][1],节点1到达节点n的严格次短路径
        for (int i = 0; i < path[n][1]; i++) {
            if (res % (2 * change) >= change) {
                res = res + (2 * change - res % (2 * change));
            }
            res = res + time;
        }
        return res;
    }

}
